package 图;

import java.util.Stack;

/**
 * @Description:
 * @Author: ywk
 * @Date: 2019/12/10 0010 21:49
 */
public class DFSGraph {
    class Vertex {
        public char label;
        public boolean visited;

        public Vertex(char label) {
            this.label = label;
            visited = false;

        }
    }

    class Graph {
        private final int maxVertices = 20;
        private Vertex[] vertexList;
        private int vertexCount;
        private int adjMatrix[][];
        private Stack<Integer> theStack;

        public Graph() {
            vertexList = new Vertex[maxVertices];
            adjMatrix = new int[maxVertices][maxVertices];
            vertexCount = 0;
            for (int y = 0; y < maxVertices; y++) {
                for (int x = 0; x < maxVertices; x++) {
                    adjMatrix[x][y] = 0;
                }
            }
            theStack = new Stack();
        }

        public void addVertex(char lab) {
            vertexList[vertexCount++] = new Vertex(lab);
        }

        public void addEdge(int start, int end) {

            adjMatrix[start][end] = 1;
            adjMatrix[end][start] = 1;
        }

        public void displayVertex(int v) {
            System.out.println(vertexList[v].label);
        }

        public void dfs() {
            for (int j = 0; j < vertexCount; j++) {
                vertexList[j].visited = false;
            }
            vertexList[0].visited=true;
            displayVertex(0);
            theStack.push(0);
            while (!theStack.isEmpty()) {

                //弹出一个未访问的顶点
                int v = getAdjUnvisitedVeterx(theStack.peek());
                if (v == -1) {
                    theStack.pop();
                }
                else{
                    vertexList[v].visited =true;
                    displayVertex(v);
                    theStack.push(v);
                }

            }


        }

        private int getAdjUnvisitedVeterx(int v) {
            for (int j = 0; j < vertexCount; j++) {
                if (adjMatrix[v][j] == 1 && vertexList[j].visited == false) {
                    return j;
                }
            }
            return -1;
        }


    }

}
